﻿#include "shujujiegou.h"
#include "ui_shujujiegou.h"
#include"author.h"
#include<QSqlQueryModel>
#include<QString>
#include<QSettings>
shujujiegou::shujujiegou(QWidget *parent) :
    QMainWindow(parent),
    ui(new Ui::shujujiegou)
{
    ui->setupUi(this);
    ui->tableView->verticalHeader()->hide();
    ui->tableView->horizontalHeader()->setSectionsClickable(false);
    ui->tableView->horizontalHeader()->setStretchLastSection(true);
    ui->tableView->setSelectionBehavior(QAbstractItemView::SelectRows);
    ui->tableView->setSelectionMode(QAbstractItemView::SingleSelection);
    ui->tableView->setEditTriggers(QAbstractItemView::NoEditTriggers);
    ui->tableView->setVerticalScrollMode(QAbstractItemView::ScrollPerPixel);
    ui->tableView->setHorizontalScrollMode(QAbstractItemView::ScrollPerPixel);
    ui->tableView->setShowGrid(false);  // disable the table grid.
    ui->tableView->verticalHeader()->setDefaultSectionSize(25);  // set row height.
    ui->tableView->horizontalHeader()->setHighlightSections(false);
    ui->tableView->setFrameShape(QFrame::NoFrame);
    connect(ui->actionC_cdex,SIGNAL(triggered(bool)),this,SLOT(showcdex()));
    connect(ui->action_head,SIGNAL(triggered(bool)),this,SLOT(showhead()));
    connect(ui->action_function,SIGNAL(triggered(bool)),this,SLOT(showfunc()));
    connect(ui->action_create,SIGNAL(triggered(bool)),this,SLOT(showcreate()));
    QPixmap pixmap = QPixmap("./image/shuju.jpg").scaled(this->size());//窗口背景图片 始
    QPalette  palette (this->palette());
    palette .setBrush(QPalette::Background, QBrush(pixmap));
    this-> setPalette( palette );//窗口背景图片 终
    ui->pushButton_exit->setIcon(QIcon("./image/exit.ico"));//设置退出按钮的图标
    setFixedSize(841,632);//设置窗口不可拉伸
    init();
    ui->actionC_cdex->setIcon(QIcon("./image/opencdex.ico"));
    ui->action_head->setIcon(QIcon("./image/openhead.ico"));
    ui->action_create->setIcon(QIcon("./image/create.ico"));
    ui->action_function->setIcon(QIcon("./image/openfunc.ico"));
    ui->pushButton_exit->setStyleSheet("QPushButton{background-color:black;color: white;   border-radius: 10px;  border: 2px groove gray;border-style: outset;}"
                                           "QPushButton:hover{background-color:white; color: black;}"

                                              "QPushButton:pressed{background-color:rgb(85, 170, 255);border-style: inset; }"

                                               );//按钮美化 黑底白字，选中变白，点击变蓝
    invite_judge();
}

shujujiegou::~shujujiegou()
{
    delete ui;
}

void shujujiegou::on_pushButton_exit_clicked()
{
    close();
}
void shujujiegou::showcdex()
{
    author a;
    a.cdexshow();
    close();
}
void shujujiegou::showhead()
{
    author a;
    a.headinfoshow();
    close();
}
void shujujiegou::init()
{
    QSqlQueryModel *model=new QSqlQueryModel;
    model->setQuery("select name as 名称 from shuju order by name");
    ui->tableView->setModel(model);
}
void shujujiegou::Show()
{
    QVariant currentData=ui->tableView->currentIndex().data();
    QSettings a("./data.ini",QSettings::IniFormat);
    if(currentData=="顺序表")
    {
        SHUNXU();
        QString info=a.value("/shuju/shunxubiao").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("shunxubiao",INFO);
        a.endGroup();
    }
    else if(currentData=="单链表")
    {
        DANLIANBIAO();
        QString info=a.value("/shuju/danlianbiao").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("danlianbiao",INFO);
        a.endGroup();
    }
    else if(currentData=="双链表")
    {
        SHUANGLIANBIAO();
        QString info=a.value("/shuju/shuanglianbiao").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("shuanglianbiao",INFO);
        a.endGroup();
    }
    else if(currentData=="AVL树")
    {
        AVL();
        QString info=a.value("/shuju/AVL").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("AVL",INFO);
        a.endGroup();
    }
    else if(currentData=="简单树")
    {
        tree();
        QString info=a.value("/shuju/jiandanshu").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("jiandanshu",INFO);
        a.endGroup();
    }
    else if(currentData=="二叉树")
    {
        erchashu();
        QString info=a.value("/shuju/erchashu").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("erchashu",INFO);
        a.endGroup();
    }
    else if(currentData=="红黑树")
    {
        redblack();
        QString info=a.value("/shuju/hongheishu").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("hongheishu",INFO);
        a.endGroup();
    }
    else if(currentData=="栈")
    {
        ZHAN();
        QString info=a.value("/shuju/zhan").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("zhan",INFO);
        a.endGroup();
    }
    else if(currentData=="堆")
    {
        DUI();
        QString info=a.value("/shuju/dui").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("dui",INFO);
        a.endGroup();
    }
    else if(currentData=="队列")
    {
        DUILIE();
        QString info=a.value("/shuju/duilie").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("duilie",INFO);
        a.endGroup();
    }
    else if(currentData=="哈夫曼树")
    {
        huffman();
        QString info=a.value("/shuju/huffman").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("huffman",INFO);
        a.endGroup();
    }
    else if(currentData=="循环链表")
    {
        XUNHUAN();
        QString info=a.value("/shuju/xunhuanlianbiao").toString();
        int INFO;
        INFO=info.toInt();
        INFO++;
        a.beginGroup("shuju");
        a.setValue("xunhuanlianbiao",INFO);
        a.endGroup();
    }
}
void shujujiegou::SHUNXU()//顺序表
{
    ui->textEdit->setText("");
    ui->textEdit->append("顺序表是在计算机内存中以数组的形式保存的线性表");
    ui->textEdit->append("线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中");
    ui->textEdit->append("即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。");
    ui->textEdit->append("顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。");
    ui->textEdit->append("而将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。");
    ui->textEdit->append("顺序表的构建和定义都比较简单，通过类和数组即可实现存储，修改和调用数据。");
    ui->textEdit ->moveCursor(QTextCursor::Start, QTextCursor::MoveAnchor);
}
void shujujiegou::on_tableView_clicked(const QModelIndex &index)
{
    Show();
}
void shujujiegou::DANLIANBIAO()
{
    ui->textEdit->setText("");
    ui->textEdit->append("  单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。");
    ui->textEdit->append("链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。");
    ui->textEdit->append("以“结点的序列”表示线性表称作线性链表（单链表）");
    ui->textEdit->append("单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。");
    ui->textEdit->append("  因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i");
    ui->textEdit->append("链接方式存储的线性表简称为链表（Linked List）。");
    ui->textEdit->append("在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。");
    ui->textEdit->append("链式存储方式即可以用于表示线性结构，也可用于表示非线性结构。");
    ui->textEdit->append("一般来说，在线性表的链式存储结构中，各数据结点的存储符号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。");
    ui->textEdit->append("对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。");

    ui->textEdit->append("  链表的具体存储表示为：");
    ui->textEdit->append("① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）");
    ui->textEdit->append("② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）");
    ui->textEdit->append("  单链表的建立有头插法、尾插法两种方法。");
    ui->textEdit->append("1．头插法");
    ui->textEdit->append("单链表是用户不断申请存储单元和改变链接关系而得到的一种特殊数据结构，将链表的左边称为链头，右边称为链尾。");
    ui->textEdit->append("头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。头插法最先得到的是尾结点。");
    ui->textEdit->append("由于链表的长度是随机的，故用一个while循环来控制链表中结点个数。假设每个结点的值都大于O，则循环条件为输入的值大于o。");
    ui->textEdit->append("申请存储空间可使用malloc()函数实现，需设立一申请单元指针，但malloc()函数得到的指针并不是指向结构体的指针，需使用强制类型转换，将其转换成结构体型指针。");
    ui->textEdit->append("刚开始时，链表还没建立，是一空链表，head指针为NULL。");
    ui->textEdit->append("链表建立的过程是申请空间、得到数据、建立链接的循环处理过程。");
    ui->textEdit->append("2．尾插法");
    ui->textEdit->append("若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。");
    ui->textEdit->append("尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针");
    ui->textEdit->append("即头指针head、搜索指针p2、申请单元指针pl。尾插法最先得到的是头结点。");
    ui->textEdit->moveCursor(QTextCursor::Start,QTextCursor::MoveAnchor);
}
void shujujiegou::SHUANGLIANBIAO()
{
    ui->textEdit->setText("");
    ui->textEdit->append("双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。");
    ui->textEdit->append("所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。");

}
void shujujiegou::AVL()
{
    ui->textEdit->setText("");
    ui->textEdit->append("在计算机科学中，AVL树是最先发明的自平衡二叉查找树。");
    ui->textEdit->append("在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。");
    ui->textEdit->append("AVL树本质上还是一棵二叉搜索树，它的特点是：");
    ui->textEdit->append("1.本身首先是一棵二叉搜索树。");
    ui->textEdit->append("2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。");
    ui->textEdit->append("也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。");
    ui->textEdit->append("AVL树的操作：");
    ui->textEdit->append("旋转");
    ui->textEdit->append("AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的""AVL 旋转""。");
    ui->textEdit->append("插入");
    ui->textEdit->append("向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。");
    ui->textEdit->append("因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。");
    ui->textEdit->append("删除");
    ui->textEdit->append("从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。");
    ui->textEdit->append("因为在旋转成叶子节点期间最多有 log n个节点被旋转，而每次 AVL 旋转耗费恒定的时间，删除处理在整体上耗费 O(log n) 时间。");
    ui->textEdit->append("查找");
    ui->textEdit->append("在AVL树中查找同在一般BST完全一样的进行，所以耗费 O(log n) 时间，因为AVL树总是保持平衡的。");
    ui->textEdit->append("不需要特殊的准备，树的结构不会由于查询而改变。（这是与伸展树查找相对立的，它会因为查找而变更树结构。）");

}
void shujujiegou::tree()
{
    ui->textEdit->setText("");
    ui->textEdit->append("树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。");
    ui->textEdit->append("把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：");
    ui->textEdit->append("每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；");
    ui->textEdit->append("除了根节点外，每个子节点可以分为多个不相交的子树；");
    ui->textEdit->append("树（tree）是包含n（n>0）个结点的有穷集，其中：");
    ui->textEdit->append("（1）每个元素称为结点（node）；");
    ui->textEdit->append("（2）有一个特定的结点被称为根结点或树根（root）。");
    ui->textEdit->append("（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。");
    ui->textEdit->append("树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。");
    ui->textEdit->append("集合中的元素称为树的结点，所定义的关系称为父子关系。");
    ui->textEdit->append("父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。");
    ui->textEdit->append("我们可以形式地给出树的递归定义如下:");
    ui->textEdit->append("单个结点是一棵树，树根就是该结点本身。");
    ui->textEdit->append("设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。");
    ui->textEdit->append("我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。空集合也是树，称为空树。空树中没有结点。");
    ui->textEdit->append("相关术语:");
    ui->textEdit->append("节点的度：一个节点含有的子树的个数称为该节点的度；");
    ui->textEdit->append("叶节点或终端节点：度为0的节点称为叶节点；");
    ui->textEdit->append("非终端节点或分支节点：度不为0的节点；");
    ui->textEdit->append("双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；");
    ui->textEdit->append("孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；");
    ui->textEdit->append("兄弟节点：具有相同父节点的节点互称为兄弟节点；");
    ui->textEdit->append("树的度：一棵树中，最大的节点的度称为树的度；");
    ui->textEdit->append("节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；");
    ui->textEdit->append("树的高度或深度：树中节点的最大层次；");
    ui->textEdit->append("堂兄弟节点：双亲在同一层的节点互为堂兄弟；");
    ui->textEdit->append("节点的祖先：从根到该节点所经分支上的所有节点；");
    ui->textEdit->append("子孙：以某节点为根的子树中任一节点都称为该节点的子孙。");
    ui->textEdit->append("森林：由m（m>=0）棵互不相交的树的集合称为森林；");
    ui->textEdit->append("深度：定义一棵树的根结点层次为1，其他节点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。");
    ui->textEdit->moveCursor(QTextCursor::Start,QTextCursor::MoveAnchor);
}
void shujujiegou::erchashu()
{
    ui->textEdit->setText("");
    ui->textEdit->append("在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。");
    ui->textEdit->append("二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。");
    ui->textEdit->append("二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；");
    ui->textEdit->append("对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。");
    ui->textEdit->append("一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。");
    ui->textEdit->append("而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。");
    ui->textEdit->append("具有n个节点的完全二叉树的深度为log2(n+1)。深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点。");
    ui->textEdit->append("特殊的二叉树：");
    ui->textEdit->append("完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。");
    ui->textEdit->append("平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。");
    ui->textEdit->append("满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。");
    ui->textEdit->append("");
    ui->textEdit->append("二叉树性质：");
    ui->textEdit->append("(1) 在非空二叉树中，第i层的结点总数不超过  , i>=1；");
    ui->textEdit->append("(2) 深度为h的二叉树最多有  个结点(h>=1)，最少有h个结点；");
    ui->textEdit->append("(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；");
    ui->textEdit->append("(4) 具有n个结点的完全二叉树的深度为  （注：[ ]表示向下取整）");
    ui->textEdit->append("(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：");
    ui->textEdit->append("若I为结点编号则 如果I>1，则其父结点的编号为I/2；");
    ui->textEdit->append("如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；");
    ui->textEdit->append("如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。");
    ui->textEdit->append("(6)给定N个节点，能构成h(N)种不同的二叉树。");
    ui->textEdit->append("h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。");
    ui->textEdit->append("(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i");
    ui->textEdit->moveCursor(QTextCursor::Start,QTextCursor::MoveAnchor);

}
void shujujiegou::redblack()
{
    ui->textEdit->setText("");
    ui->textEdit->append("红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。");
    ui->textEdit->append("它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。");
    ui->textEdit->append("红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。");
    ui->textEdit->append("它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。");
    ui->textEdit->append("它的统计性能要好于平衡二叉树,因此，红黑树在很多地方都有应用。");
    ui->textEdit->append("在C++ STL中，很多部分(包括set, multiset, map, multimap)应用了红黑树的变体，这些修改提供了更好的性能，以及对set操作的支持。");
    ui->textEdit->append("红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:");
    ui->textEdit->append("性质1. 节点是红色或黑色。");
    ui->textEdit->append("性质2. 根节点是黑色。");
    ui->textEdit->append("性质3 每个叶节点（NIL节点，空节点）是黑色的。");
    ui->textEdit->append("性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)");
    ui->textEdit->append("性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。");
    ui->textEdit->append("这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。");
    ui->textEdit->append("因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。");
    ui->textEdit->append("由于红黑树也是二叉查找树，它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。");
    ui->textEdit->moveCursor(QTextCursor::Start,QTextCursor::MoveAnchor);
}

void shujujiegou::on_lineEdit_textChanged(const QString &arg1)
{
    QSqlQueryModel *model=new QSqlQueryModel;
    QString a,b;

    b=ui->lineEdit->text();
    a="select name as 名称 from shuju where name LIKE '%"+b+"%'";
    model->setQuery(a);
    ui->tableView->setModel(model);
}
void shujujiegou::ZHAN()
{
    ui->textEdit->setText("");
    ui->textEdit->append("栈（stack），它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。");
    ui->textEdit->append("这一端被称为栈顶，相对地，把另一端称为栈底。");
    ui->textEdit->append("向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；");
    ui->textEdit->append("从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。");
    ui->textEdit->append("定义：栈是限定仅在表头进行插入和删除操作的线性表。要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。");
    ui->textEdit->append("栈,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。");
    ui->textEdit->append("栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据");
    ui->textEdit->append("先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来。");
    ui->textEdit->append("栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。");
    ui->textEdit->append("栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。");
    ui->textEdit->append("插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。");
    ui->textEdit->append("栈可以用来在函数调用的时候存储断点，做递归时要用到栈.");
    ui->textEdit->append("栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：");
    ui->textEdit->append("1．函数的返回地址和参数");
    ui->textEdit->append("2． 临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。");
    ui->textEdit->append("基本算法：");
    ui->textEdit->append("1．进栈（PUSH）算法");
    ui->textEdit->append("①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；");
    ui->textEdit->append("②置TOP=TOP+1（栈指针加1，指向进栈地址）；");
    ui->textEdit->append("③S(TOP)=X，结束（X为新进栈的元素）；");
    ui->textEdit->append("2．退栈（POP）算法");
    ui->textEdit->append("①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；");
    ui->textEdit->append("②X=S(TOP)，（退栈后的元素赋给X）：");
    ui->textEdit->append("③TOP=TOP-1，结束（栈指针减1，指向栈顶）。");
    ui->textEdit->moveCursor(QTextCursor::Start,QTextCursor::MoveAnchor);

}
void shujujiegou::DUI()
{
    ui->textEdit->setText("");
    ui->textEdit->append("堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：");
    ui->textEdit->append("堆中某个节点的值总是不大于或不小于其父节点的值；");
    ui->textEdit->append("堆总是一棵完全二叉树。");
    ui->textEdit->append("将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。");
    ui->textEdit->append("堆支持以下的基本:");
    ui->textEdit->append("build:建立一个空堆；");
    ui->textEdit->append("insert:向堆中插入一个新元素；");
    ui->textEdit->append("update：将新元素提升使其符合堆的性质；");
    ui->textEdit->append("get：获取当前堆顶元素的值；");
    ui->textEdit->append("delete：删除堆顶元素；");
    ui->textEdit->append("heapify：使删除堆顶元素的堆再次成为堆。");
    ui->textEdit->append("算法思想");
    ui->textEdit->append("不必将值一个个地插入堆中，通过交换形成堆。假设根的左、右子树都已是堆，并且根的元素名为R。这种情况下，有两种可能：");
    ui->textEdit->append("（1） R的值小于或等于其两个子女，此时堆已完成；");
    ui->textEdit->append("（2） R的值大于其某一个或全部两个子女的值，此时R应与两个子女中值较小的一个交换，结果得到一个堆，除非R仍然大于其新子女的一个或全部的两个。");
    ui->textEdit->append("这种情况下，我们只需简单地继续这种将R“拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。");
    ui->textEdit->append("建堆效率:");
    ui->textEdit->append("n个结点的堆，高度d =log2n。根为第0层，则第i层结点个数为2i，考虑一个元素在堆中向下移动的距离。大约一半的结点深度为d-1，不移动（叶）。");
    ui->textEdit->append("四分之一的结点深度为d-2，而它们至多能向下移动一层。树中每向上一层，结点的数目为前一层的一半，而子树高度加一。");
    ui->textEdit->append("这种算法时间代价为Ο（n)");
    ui->textEdit->append("由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是Ο（log n）。");
    ui->textEdit->append("操作实现：");
    ui->textEdit->append("在程序中，堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作：");
    ui->textEdit->append("1.事先不知道程序所需对象的数量和大小。");
    ui->textEdit->append("2.对象太大，不适合使用堆栈分配器。");
    ui->textEdit->append("堆使用运行期间分配给代码和堆栈以外的部分内存。");
    ui->textEdit->append("传统上，操作系统和运行时库随附了堆实现。当进程开始时，操作系统创建称为进程堆的默认堆。如果没有使用其他堆，则使用进程堆分配块。语言运行时库也可在一个进程内创建单独的堆。");
    ui->textEdit->append("当应用程序或 DLL 创建专用堆时，这些堆驻留于进程空间中并且在进程范围内是可访问的。某一给定堆分配的任何数据应为同一堆所释放。");
    ui->textEdit->append("在所有虚拟内存系统中，堆位于操作系统的虚拟内存管理器之上。语言运行时堆也驻留在虚拟内存之上。某些情况下，这些堆在操作系统堆的上层，但语言运行时堆通过分配大的块来执行自己的内存管理。");
    ui->textEdit->append("绕开操作系统堆来使用虚拟内存函数可使堆更好地分配和使用块。");
    ui->textEdit->append("典型的堆实现由前端分配器和后端分配器组成。前端分配器维护固定大小块的自由列表。当堆收到分配调用后，它尝试从前端列表中查找自由块。");
    ui->textEdit->append("如果此操作失败，则堆将被迫从后端（保留和提交虚拟内存）分配一个大块来满足请求。通常的实现具有每个块分配的开销，这花费了执行周期，也减少了可用存储区。");
    ui->textEdit->append("单个全局锁可防止多线程同时使用堆。此锁主要用于保护堆数据结构不受多线程的任意访问。当堆操作过于频繁时，此锁会对性能造成负面影响。");

    ui->textEdit->moveCursor(QTextCursor::Start,QTextCursor::MoveAnchor);
}
void shujujiegou::DUILIE()
{
    ui->textEdit->setText("");
    ui->textEdit->append("队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作");
    ui->textEdit->append("而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。");
    ui->textEdit->append("队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。");
    ui->textEdit->append("进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。");
    ui->textEdit->append("队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除");
    ui->textEdit->append("所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。");
    ui->textEdit->append("顺序队列:");
    ui->textEdit->append("建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置");
    ui->textEdit->append("每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化");
    ui->textEdit->append("队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。");
    ui->textEdit->append("当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。");
    ui->textEdit->append("顺序队列中的溢出现象：");
    ui->textEdit->append("（1） ""下溢""现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。");
    ui->textEdit->append("（2）""真上溢""现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。");
    ui->textEdit->append("（3）""假上溢""现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时");
    ui->textEdit->append("也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为""假上溢""现象。");
    ui->textEdit->append("循环队列:");
    ui->textEdit->append("在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。");
    ui->textEdit->append("自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。");
    ui->textEdit->append("这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。");
    ui->textEdit->append("在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，");
    ui->textEdit->append("规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。");
    ui->textEdit->append("因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。");
    ui->textEdit->moveCursor(QTextCursor::Start,QTextCursor::MoveAnchor);

}
void shujujiegou::huffman()
{
    ui->textEdit->setText("");
    ui->textEdit->append("给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。");
    ui->textEdit->append("哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。");
    ui->textEdit->append("应用：");
    ui->textEdit->append("1、哈夫曼编码");
    ui->textEdit->append("为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，");
    ui->textEdit->append("可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下，");
    ui->textEdit->append("于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。");
    ui->textEdit->append("因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。");
    ui->textEdit->append("利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。");
    ui->textEdit->append("哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来");
    ui->textEdit->append("哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的");
    ui->textEdit->append("2、哈夫曼译码");
    ui->textEdit->append("在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。");
    ui->textEdit->append("基本术语：");
    ui->textEdit->append("哈夫曼树（霍夫曼树）又称为最优树");
    ui->textEdit->append("1、路径和路径长度");
    ui->textEdit->append("在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。");
    ui->textEdit->append("2、结点的权及带权路径长度");
    ui->textEdit->append("若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。");
    ui->textEdit->append("3、树的带权路径长度");
    ui->textEdit->append("树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。");
    ui->textEdit->moveCursor(QTextCursor::Start,QTextCursor::MoveAnchor);

}
void shujujiegou::XUNHUAN()
{
    ui->textEdit->setText("");
    ui->textEdit->append("循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。");
    ui->textEdit->append("");
    ui->textEdit->append("分类:");
    ui->textEdit->append("（1）单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。");
    ui->textEdit->append("（2）多重链的循环链表——将表中结点链在多个环上。");
    ui->textEdit->append("");
    ui->textEdit->append("空链判断:");
    ui->textEdit->append("判断空链表的条件是");
    ui->textEdit->append("head==head->next;");
    ui->textEdit->append("rear==rear->next;");
    ui->textEdit->append("循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。");

}
void shujujiegou::showfunc()
{
    author a;
    a.funcshow();
    close();
}
void shujujiegou::invite()
{
    if(maxS=="shunxubiao")
    {
        SHUNXU();
        maxS="顺序表";
    }
    else if(maxS=="shuanglianbiao")
    {
        SHUANGLIANBIAO();
        maxS="双链表";
    }
    else if(maxS=="zhan")
    {
        ZHAN();
        maxS="栈";
    }
    else if(maxS=="duilie")
    {
        DUILIE();
        maxS="队列";
    }
    else if(maxS=="dui")
    {
        DUI();
        maxS="堆";
    }
    else if(maxS=="erchashu")
    {
        erchashu();
        maxS="二叉树";
    }
    else if(maxS=="hongheishu")
    {
        redblack();
        maxS="红黑树";
    }
    else if(maxS=="AVL")
    {
        AVL();
        maxS="AVL树";
    }
    else if(maxS=="huffman")
    {
        huffman();
        maxS="哈夫曼树";
    }
    else if(maxS=="xunhuanlianbiao")
    {
        XUNHUAN();
        maxS="循环链表";
    }
    else if(maxS=="danlianbiao")
    {
        DANLIANBIAO();
        maxS="单链表";

    }
    else if(maxS=="jiandanshu")
    {
        tree();
        maxS="简单树";
    }
}
void shujujiegou::invite_judge()
{
    invite_set();
    if(max!=0)
    {
       invite();
       QString a1;
       a1="你最常查看的搜索项是："+maxS+"\n现在开始自动推送";
       QMessageBox::about(NULL, "智能推荐", a1);

    }
}
void shujujiegou::invite_set()
{
    int INFO;

    QSettings invi("./data.ini",QSettings::IniFormat);
    QString info=invi.value("/shuju/shunxubiao").toString();

    INFO=info.toInt();


    if(max<INFO)
    {
        max=INFO;
        maxS="shunxubiao";
    }
    info=invi.value("/shuju/shuanglianbiao").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="shuanglianbiao";
    }
    info=invi.value("/shuju/zhan").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="zhan";
    }
    info=invi.value("/shuju/duilie").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="duilie";
    }
    info=invi.value("/shuju/dui").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="dui";
    }
    info=invi.value("/shuju/erchashu").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="erchashu";
    }
    info=invi.value("/shuju/hongheishu").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="hongheishu";
    }
    info=invi.value("/shuju/AVL").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="AVL";
    }
    info=invi.value("/shuju/huffman").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="huffman";
    }
    info=invi.value("/shuju/xunhuanlianbiao").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="xunhuanlianbiao";
    }
    info=invi.value("/shuju/danlianbiao").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="danlianbiao";
    }
    info=invi.value("/shuju/jiandanshu").toString();

    INFO=info.toInt();

    if(max<INFO)
    {
        max=INFO;
        maxS="jiandanshu";
    }
}
void shujujiegou::showcreate()
{
    hide();
    author a;
    a.createshow();
}
